package com.sicheng.lc.周赛.分类.dp.线性;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/3 11:32
 */
public class 知道秘密的人数 {
    static int mod = (int) (1e9 + 7);

    //https://leetcode.cn/contest/weekly-contest-300/problems/number-of-people-aware-of-a-secret/
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (i + delay > n)
                cnt = (cnt + dp[i]) % mod;
            for (int j = i + delay; j <= Math.min(n, i + forget - 1); j++) {
                dp[j] = (dp[j] + dp[i]) % mod;
            }
        }
        return (dp[n] + cnt) % mod;
    }

    public static void main(String[] args) {
        知道秘密的人数 s = new 知道秘密的人数();
        System.out.println(s.peopleAwareOfSecret(5, 2, 3));
    }
}
